/*
 * @lc app=leetcode.cn id=300 lang=javascript
 *
 * [300] 最长上升子序列
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
  const size = nums.length;
  // 单调递增的上升子序列
  const result = [nums[0]];

  for (let i = 1; i < size; i++) {
    if (nums[i] > result[result.length - 1]) {
      result.push(nums[i]);
    } else {
      // 二分查找，替换掉result中最接近并大于nums[i]的值
      let left = 0;
      let right = result.length - 1;
      while (left < right) {
        let mid = left + ((right - left) >> 1);
        if (result[mid] < nums[i]) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      result[left] = nums[i];
    }
  }

  return result.length;
};
// @lc code=end
